package com.leetcode;
//在一个 下标从 0 开始 的 8 x 8 棋盘上，可能有多个黑皇后和一个白国王。
//
// 给你一个二维整数数组 queens，其中 queens[i] = [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度
//为 2 的整数数组 king，其中 king = [xKing, yKing] 表示白国王的位置。
//
// 返回 能够直接攻击国王的黑皇后的坐标。你可以以 任何顺序 返回答案。
//
//
//
// 示例 1：
//
//
//
//
//输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
//输出：[[0,1],[1,0],[3,3]]
//解释：上面的图示显示了三个可以直接攻击国王的皇后和三个不能攻击国王的皇后（用红色虚线标记）。
//
//
// 示例 2：
//
//
//
//
//输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
//输出：[[2,2],[3,4],[4,4]]
//解释：上面的图示显示了三个能够直接攻击国王的黑皇后和三个不能攻击国王的黑皇后（用红色虚线标记）。
//
//
//
// 提示：
//
//
//
// 1 <= queens.length < 64
// queens[i].length == king.length == 2
// 0 <= xQueeni, yQueeni, xKing, yKing < 8
// 所有给定的位置都是 唯一 的。
//
//
// Related Topics 数组 矩阵 模拟 👍 128 👎 0


import javax.management.MBeanAttributeInfo;
import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class No1222 {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        boolean[][] board = new boolean[8][8];
        for (int i = 0; i < queens.length; i++) {
            int[] queen = queens[i];
            board[queen[0]][queen[1]] = true;
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < queens.length; i++) {
            int[] queen = queens[i];
            if (queen[0] == king[0]) {
                int start = Math.min(queen[1], king[1]) + 1;
                int end = Math.max(queen[1], king[1]);
                boolean found = false;
                for (int j = start; j < end; j++) {
                    if (board[queen[0]][j]) {
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    list.add(List.of(queen[0], queen[1]));
                }
            } else if (queen[1] == king[1]) {
                int start = Math.min(queen[0], king[0]) + 1;
                int end = Math.max(queen[0], king[0]);
                boolean found = false;
                for (int j = start; j < end; j++) {
                    if (board[j][queen[1]]) {
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    list.add(List.of(queen[0], queen[1]));
                }
            } else if (Math.abs(queen[0] - king[0]) == Math.abs(queen[1] - king[1])) {
                int step = Math.abs(queen[0] - king[0]) - 1;
                int x = queen[0] > king[0] ? -1 : 1;
                int y = queen[1] > king[1] ? -1 : 1;
                boolean found = false;
                for (int j = 1; j <= step; j++) {
                    if (board[j * x + queen[0]][y * j + queen[1]]) {
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    list.add(List.of(queen[0], queen[1]));
                }
            }
        }
        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
